/*
 * Copyright (c) 2006-2007 Erin Catto http://www.gphysics.com
 *
 * This software is provided 'as-is', without any express or implied
 * warranty.  In no event will the authors be held liable for any damages
 * arising from the use of this software.
 * Permission is granted to anyone to use this software for any purpose,
 * including commercial applications, and to alter it and redistribute it
 * freely, subject to the following restrictions:
 * 1. The origin of this software must not be misrepresented; you must not
 * claim that you wrote the original software. If you use this software
 * in a product, an acknowledgment in the product documentation would be
 * appreciated but is not required.
 * 2. Altered source versions must be plainly marked as such, and must not be
 * misrepresented as being the original software.
 * 3. This notice may not be removed or altered from any source distribution.
 */

package org.box2dflash.collision.shapes {
	import org.box2dflash.common.math.*;
	import org.box2dflash.common.*;
	import org.box2dflash.collision.shapes.*;
	import org.box2dflash.collision.*;
	use namespace Internal;

	/// Convex polygon. The vertices must be in CCW order for a right-handed
	/// coordinate system with the z-axis coming out of the screen.
	public class PolygonShape extends Shape {
		/// @see Shape::TestPoint
		public override function testPoint(xf:XForm, p:Vec2):Boolean {
			var tVec:Vec2;
		
			//Vec2 pLocal = MulT(xf.R, p - xf.position);
			var tMat:Mat22 = xf.R;
			var tX:Number = p.x - xf.position.x;
			var tY:Number = p.y - xf.position.y;
			var pLocalX:Number = (tX * tMat.col1.x + tY * tMat.col1.y);
			var pLocalY:Number = (tX * tMat.col2.x + tY * tMat.col2.y);
		
			for (var i:int = 0;i < m_vertexCount; ++i) {
				//float32 dot = Dot(m_normals[i], pLocal - m_vertices[i]);
				tVec = m_vertices[i];
				tX = pLocalX - tVec.x;
				tY = pLocalY - tVec.y;
				tVec = m_normals[i];
				var dot:Number = (tVec.x * tX + tVec.y * tY);
				if (dot > 0.0) {
					return false;
				}
			}
		
			return true;
		}

		/// @see Shape::TestSegment
		public override function testSegment( xf:XForm,
		lambda:Array, // float ptr
		normal:Vec2, // ptr
		segment:Segment,
		maxLambda:Number):Boolean {
			var lower:Number = 0.0;
			var upper:Number = maxLambda;
		
			var tX:Number;
			var tY:Number;
			var tMat:Mat22;
			var tVec:Vec2;
		
			//Vec2 p1 = MulT(xf.R, segment.p1 - xf.position);
			tX = segment.p1.x - xf.position.x;
			tY = segment.p1.y - xf.position.y;
			tMat = xf.R;
			var p1X:Number = (tX * tMat.col1.x + tY * tMat.col1.y);
			var p1Y:Number = (tX * tMat.col2.x + tY * tMat.col2.y);
			//Vec2 p2 = MulT(xf.R, segment.p2 - xf.position);
			tX = segment.p2.x - xf.position.x;
			tY = segment.p2.y - xf.position.y;
			tMat = xf.R;
			var p2X:Number = (tX * tMat.col1.x + tY * tMat.col1.y);
			var p2Y:Number = (tX * tMat.col2.x + tY * tMat.col2.y);
			//Vec2 d = p2 - p1;
			var dX:Number = p2X - p1X;
			var dY:Number = p2Y - p1Y;
			var index:int = -1;
		
			for (var i:int = 0;i < m_vertexCount; ++i) {
				// p = p1 + a * d
				// dot(normal, p - v) = 0
				// dot(normal, p1 - v) + a * dot(normal, d) = 0
			
				//float32 numerator = Dot(m_normals[i], m_vertices[i] - p1);
				tVec = m_vertices[i];
				tX = tVec.x - p1X;
				tY = tVec.y - p1Y;
				tVec = m_normals[i];
				var numerator:Number = (tVec.x * tX + tVec.y * tY);
				//float32 denominator = Dot(m_normals[i], d);
				var denominator:Number = (tVec.x * dX + tVec.y * dY);
			
				// Note: we want this predicate without division:
				// lower < numerator / denominator, where denominator < 0
				// Since denominator < 0, we have to flip the inequality:
				// lower < numerator / denominator <==> denominator * lower > numerator.
				if (denominator < 0.0 && numerator < lower * denominator) {
					// Increase lower.
					// The segment enters this half-space.
					lower = numerator / denominator;
					index = i;
				}
			else if (denominator > 0.0 && numerator < upper * denominator) {
					// Decrease upper.
					// The segment exits this half-space.
					upper = numerator / denominator;
				}
			
				if (upper < lower) {
					return false;
				}
			}
		
			//Settings.Assert(0.0 <= lower && lower <= maxLambda);
			if (index >= 0) {
				//*lambda = lower;
				lambda[0] = lower;
				//*normal = Mul(xf.R, m_normals[index]);
				tMat = xf.R;
				tVec = m_normals[index];
				normal.x = (tMat.col1.x * tVec.x + tMat.col2.x * tVec.y);
				normal.y = (tMat.col1.y * tVec.x + tMat.col2.y * tVec.y);
				return true;
			}
		
			return false;
		}

		/// @see Shape::ComputeAABB
		//
		static private var s_computeMat:Mat22 = new Mat22();

		//
		public override function computeAABB(aabb:AABB, xf:XForm):void {
			var tMat:Mat22;
			var tVec:Vec2;
		
			var R:Mat22 = s_computeMat;
			//Mat22 R = Mul(xf.R, m_obb.R);
			tMat = xf.R;
			tVec = m_obb.R.col1;
			//R.col1 = MulMV(A, B.col1)
			R.col1.x = (tMat.col1.x * tVec.x + tMat.col2.x * tVec.y);
			R.col1.y = (tMat.col1.y * tVec.x + tMat.col2.y * tVec.y);
			//
			tVec = m_obb.R.col2;
			//R.col1 = MulMV(A, B.col2)
			R.col2.x = (tMat.col1.x * tVec.x + tMat.col2.x * tVec.y);
			R.col2.y = (tMat.col1.y * tVec.x + tMat.col2.y * tVec.y);
		
			//Mat22 absR = Abs(R);
			R.abs();
			var absR:Mat22 = R;
			//Vec2 h = Mul(absR, m_obb.extents);
			tVec = m_obb.extents;
			var hX:Number = (absR.col1.x * tVec.x + absR.col2.x * tVec.y);
			var hY:Number = (absR.col1.y * tVec.x + absR.col2.y * tVec.y);
			//Vec2 position = xf.position + Mul(xf.R, m_obb.center);
			tMat = xf.R;
			tVec = m_obb.center;
			var positionX:Number = xf.position.x + (tMat.col1.x * tVec.x + tMat.col2.x * tVec.y);
			var positionY:Number = xf.position.y + (tMat.col1.y * tVec.x + tMat.col2.y * tVec.y);
			//aabb->lowerBound = position - h;
			aabb.lowerBound = new Vec2(positionX - hX, positionY - hY);
			//aabb->upperBound = position + h;
			aabb.upperBound = new Vec2(positionX + hX, positionY + hY);
		}

		/// @see Shape::ComputeSweptAABB
		//
		static private var s_sweptAABB1:AABB = new AABB();
		static private var s_sweptAAB:AABB = new AABB();

		//
		public override function computeSweptAABB(	aabb:AABB,
		transform1:XForm,
		transform2:XForm):void {
			//AABB aabb1, aab;
			var aabb1:AABB = s_sweptAABB1;
			var aab:AABB = s_sweptAAB;
			computeAABB(aabb1, transform1);
			computeAABB(aab, transform2);
			//aabb.lowerBound = Min(aabb1.lowerBound, aab.lowerBound);
			aabb.lowerBound = new Vec2((aabb1.lowerBound.x < aab.lowerBound.x ? aabb1.lowerBound.x : aab.lowerBound.x), (aabb1.lowerBound.y < aab.lowerBound.y ? aabb1.lowerBound.y : aab.lowerBound.y));
			//aabb.upperBound = Max(aabb1.upperBound, aab.upperBound);
			aabb.upperBound = new Vec2((aabb1.upperBound.x > aab.upperBound.x ? aabb1.upperBound.x : aab.upperBound.x), (aabb1.upperBound.y > aab.upperBound.y ? aabb1.upperBound.y : aab.upperBound.y));
		}

		/// @see Shape::ComputeMass
		//
	
		//
		public override function computeMass(massData:MassData):void {
			// Polygon mass, centroid, and inertia.
			// Let rho be the polygon density in mass per unit area.
			// Then:
			// mass = rho * int(dA)
			// centroid.x = (1/mass) * rho * int(x * dA)
			// centroid.y = (1/mass) * rho * int(y * dA)
			// I = rho * int((x*x + y*y) * dA)
			//
			// We can compute these integrals by summing all the integrals
			// for each triangle of the polygon. To evaluate the integral
			// for a single triangle, we make a change of variables to
			// the (u,v) coordinates of the triangle:
			// x = x0 + e1x * u + e2x * v
			// y = y0 + e1y * u + e2y * v
			// where 0 <= u && 0 <= v && u + v <= 1.
			//
			// We integrate u from [0,1-v] and then v from [0,1].
			// We also need to use the Jacobian of the transformation:
			// D = cross(e1, e2)
			//
			// Simplification: triangle centroid = (1/3) * (p1 + p2 + p3)
			//
			// The rest of the derivation is handled by computer algebra.
		
			//Settings.Assert(m_vertexCount >= 3);
		
			//Vec2 center; center = new Vec2(0.0f, 0.0f);
			var centerX:Number = 0.0;
			var centerY:Number = 0.0;
			var area:Number = 0.0;
			var I:Number = 0.0;
		
			// pRef is the reference point for forming triangles.
			// It's location doesn't change the result (except for rounding error).
			//Vec2 pRef(0.0f, 0.0f);
			var p1X:Number = 0.0;
			var p1Y:Number = 0.0;
			/*#if 0
			// This code would put the reference point inside the polygon.
			for (int32 i = 0; i < m_vertexCount; ++i)
			{
			pRef += m_vertices[i];
			}
			pRef *= 1.0f / count;
			#endif*/
			var k_inv3:Number = 1.0 / 3.0;
		
			for (var i:int = 0;i < m_vertexCount; ++i) {
				// Triangle vertices.
				//Vec2 p1 = pRef;
				//
				//Vec2 p2 = m_vertices[i];
				var p2:Vec2 = m_vertices[i];
				//Vec2 p3 = i + 1 < m_vertexCount ? m_vertices[i+1] : m_vertices[0];
				var p3:Vec2 = i + 1 < m_vertexCount ? m_vertices[int(i + 1)] : m_vertices[0];
			
				//Vec2 e1 = p2 - p1;
				var e1X:Number = p2.x - p1X;
				var e1Y:Number = p2.y - p1Y;
				//Vec2 e2 = p3 - p1;
				var e2X:Number = p3.x - p1X;
				var e2Y:Number = p3.y - p1Y;
			
				//float32 D = Cross(e1, e2);
				var D:Number = e1X * e2Y - e1Y * e2X;
			
				//float32 triangleArea = 0.5f * D;
				var triangleArea:Number = 0.5 * D;
				area += triangleArea;
			
				// Area weighted centroid
				//center += triangleArea * k_inv3 * (p1 + p2 + p3);
				centerX += triangleArea * k_inv3 * (p1X + p2.x + p3.x);
				centerY += triangleArea * k_inv3 * (p1Y + p2.y + p3.y);
			
				//float32 px = p1.x, py = p1.y;
				var px:Number = p1X;
				var py:Number = p1Y;
				//float32 ex1 = e1.x, ey1 = e1.y;
				var ex1:Number = e1X;
				var ey1:Number = e1Y;
				//float32 ex2 = e2.x, ey2 = e2.y;
				var ex2:Number = e2X;
				var ey2:Number = e2Y;
			
				//float32 intx2 = k_inv3 * (0.25f * (ex1*ex1 + ex2*ex1 + ex2*ex2) + (px*ex1 + px*ex2)) + 0.5f*px*px;
				var intx2:Number = k_inv3 * (0.25 * (ex1 * ex1 + ex2 * ex1 + ex2 * ex2) + (px * ex1 + px * ex2)) + 0.5 * px * px;
				//float32 inty2 = k_inv3 * (0.25f * (ey1*ey1 + ey2*ey1 + ey2*ey2) + (py*ey1 + py*ey2)) + 0.5f*py*py;
				var inty2:Number = k_inv3 * (0.25 * (ey1 * ey1 + ey2 * ey1 + ey2 * ey2) + (py * ey1 + py * ey2)) + 0.5 * py * py;
			
				I += D * (intx2 + inty2);
			}
		
			// Total mass
			massData.mass = m_density * area;
		
			// Center of mass
			//Settings.Assert(area > Number.MIN_VALUE);
			//center *= 1.0f / area;
			centerX *= 1.0 / area;
			centerY *= 1.0 / area;
			//massData->center = center;
			massData.center = new Vec2(centerX, centerY);
		
			// Inertia tensor relative to the local origin.
			massData.I = m_density * I;
		}

		/// Get the oriented bounding box relative to the parent body.
		public function get oBB():OBB {
			return m_obb;
		}

		/// Get local centroid relative to the parent body.
		public function get centroid():Vec2 {
			return m_centroid;
		}

		/// Get the vertex count.
		public function get vertexCount():int {
			return m_vertexCount;
		}

		/// Get the vertices in local coordinates.
		public function get vertices():Array {
			return m_vertices;
		}

		/// Get the core vertices in local coordinates. These vertices
		/// represent a smaller polygon that is used for time of impact
		/// computations.
		public function get coreVertices():Array {
			return m_coreVertices;
		}

		/// Get the edge normal vectors. There is one for each vertex.
		public function get normals():Array {
			return m_normals;
		}

		/// Get the first vertex and apply the supplied transform.
		public function firstVertex(xf:XForm):Vec2 {
			return Box2dMath.mulX(xf, m_coreVertices[0]);
		}

		/// Get the centroid and apply the supplied transform.
		public function getCentroid(xf:XForm):Vec2 {
			return Box2dMath.mulX(xf, m_centroid);
		}

		/// Get the support point in the given world direction.
		/// Use the supplied transform.
		private var s_supportVec:Vec2 = new Vec2();

		public function support(xf:XForm, dX:Number, dY:Number):Vec2 {
			var tVec:Vec2;
		
			var tMat:Mat22;
			//Vec2 dLocal = MulT(xf.R, d);
			tMat = xf.R;
			var dLocalX:Number = (dX * tMat.col1.x + dY * tMat.col1.y);
			var dLocalY:Number = (dX * tMat.col2.x + dY * tMat.col2.y);
		
			var bestIndex:int = 0;
			//var bestValue:Number = Dot(m_coreVertices[0], dLocal);
			tVec = m_coreVertices[0];
			var bestValue:Number = (tVec.x * dLocalX + tVec.y * dLocalY);
			for (var i:int = 1;i < m_vertexCount; ++i) {
				//var value:Number = Dot(m_coreVertices[i], dLocal);
				tVec = m_coreVertices[i];
				var value:Number = (tVec.x * dLocalX + tVec.y * dLocalY);
				if (value > bestValue) {
					bestIndex = i;
					bestValue = value;
				}
			}
		
			//return Box2dMath.MulX(xf, m_coreVertices[bestIndex]);
			tMat = xf.R;
			tVec = m_coreVertices[bestIndex];
			s_supportVec.x = xf.position.x + (tMat.col1.x * tVec.x + tMat.col2.x * tVec.y);
			s_supportVec.y = xf.position.y + (tMat.col1.y * tVec.x + tMat.col2.y * tVec.y);
			return s_supportVec;
		}

		//--------------- Internals Below -------------------
		public function PolygonShape(def:ShapeDef) {
			super(def);
		
			//Settings.Assert(def.type == e_polygonShape);
			m_type = e_polygonShape;
			var poly:PolygonDef = def as PolygonDef;
		
			// Get the vertices transformed into the body frame.
			m_vertexCount = poly.vertexCount;
			//Settings.Assert(3 <= m_vertexCount && m_vertexCount <= _maxPolygonVertices);
			var i:int;
			var i1:int = i;
			var i2:int = i;
		
			// Copy vertices.
			for (i = 0;i < m_vertexCount; ++i) {
				m_vertices[i] = poly.vertices[i].copy;
			}
		
			// Compute normals. Ensure the edges have non-zero length.
			for (i = 0;i < m_vertexCount; ++i) {
				i1 = i;
				i2 = i + 1 < m_vertexCount ? i + 1 : 0;
				//Vec2 edge = m_vertices[i2] - m_vertices[i1];
				var edgeX:Number = m_vertices[i2].x - m_vertices[i1].x;
				var edgeY:Number = m_vertices[i2].y - m_vertices[i1].y;
				//Settings.Assert(edgeLengthSquared > Number.MIN_VALUE * Number.MIN_VALUE);
				//m_normals[i] = Cross(edge, 1.0f); ^^ 
				var len:Number = Math.sqrt(edgeX * edgeX + edgeY * edgeY);
				//m_normals[i].Normalize();
				m_normals[i] = new Vec2(edgeY / len, -edgeX / len);
			}
		
			/*#ifdef _DEBUG
			// Ensure the polygon is convex.
			for (int32 i = 0; i < m_vertexCount; ++i)
			{
			for (int32 j = 0; j < m_vertexCount; ++j)
			{
			// Don't check vertices on the current edge.
			if (j == i || j == (i + 1) % m_vertexCount)
			{
			continue;
			}
				
			// Your polygon is non-convex (it has an indentation).
			// Or your polygon is too skinny.
			float32 s = Dot(m_normals[i], m_vertices[j] - m_vertices[i]);
			Assert(s < -_linearSlop);
			}
			}
		
			// Ensure the polygon is counter-clockwise.
			for (i = 1; i < m_vertexCount; ++i)
			{
			var cross:Number = Box2dMath.CrossVV(m_normals[int(i-1)], m_normals[i]);
			
			// Keep asinf happy.
			cross = Box2dMath.Clamp(cross, -1.0, 1.0);
			
			// You have consecutive edges that are almost parallel on your polygon.
			var angle:Number = Box2dMath.asin(cross);
			//Assert(angle > _angularSlop);
			trace(angle > Settings._angularSlop);
			}
			#endif*/
		
			// Compute the polygon centroid.
			m_centroid = computeCentroid(poly.vertices, poly.vertexCount);
		
			// Compute the oriented bounding box.
			computeOBB(m_obb, m_vertices, m_vertexCount);
		
			// Create core polygon shape by shifting edges inward.
			// Also compute the min/max radius for CCD.
			for (i = 0;i < m_vertexCount; ++i) {
				i1 = i - 1 >= 0 ? i - 1 : m_vertexCount - 1;
				i2 = i;
			
				//Vec2 n1 = m_normals[i1];
				var n1X:Number = m_normals[i1].x;
				var n1Y:Number = m_normals[i1].y;
				//Vec2 n2 = m_normals[i2];
				var n2X:Number = m_normals[i2].x;
				var n2Y:Number = m_normals[i2].y;
				//Vec2 v = m_vertices[i] - m_centroid;
				var vX:Number = m_vertices[i].x - m_centroid.x;
				var vY:Number = m_vertices[i].y - m_centroid.y;
			
				//Vec2 d;
				var dX:Number = (n1X * vX + n1Y * vY) - Settings._toiSlop;
				var dY:Number = (n2X * vX + n2Y * vY) - Settings._toiSlop;
			
				// Shifting the edge inward by _toiSlop should
				// not cause the plane to pass the centroid.
			
				// Your shape has a radius/extent less than _toiSlop.
				//Settings.Assert(d.x >= 0.0);
				//Settings.Assert(d.y >= 0.0);
				//var A:Mat22;
				//A.col1.x = n1.x; A.col2.x = n1.y;
				//A.col1.y = n2.x; A.col2.y = n2.y;
				//m_coreVertices[i] = A.Solve(d) + m_centroid;
				//float32 det = a11 * a22 - a12 * a21;
				var det:Number = 1.0 / (n1X * n2Y - n1Y * n2X);
				//det = 1.0 / det;
				m_coreVertices[i] = new Vec2(det * (n2Y * dX - n1Y * dY) + m_centroid.x, det * (n1X * dY - n2X * dX) + m_centroid.y);
			}
		}

		Internal override function updateSweepRadius(center:Vec2):void {
			var tVec:Vec2;
		
			// Update the sweep radius (maximum radius) as measured from
			// a local center point.
			m_sweepRadius = 0.0;
			for (var i:int = 0;i < m_vertexCount; ++i) {
				//Vec2 d = m_coreVertices[i] - center;
				tVec = m_coreVertices[i];
				var dX:Number = tVec.x - center.x;
				var dY:Number = tVec.y - center.y;
				dX = Math.sqrt(dX * dX + dY * dY);
				//m_sweepRadius = Max(m_sweepRadius, d.length);
				if (dX > m_sweepRadius) m_sweepRadius = dX;
			}
		}

		// Local position of the polygon centroid.
		Internal var m_centroid:Vec2;
		Internal var m_obb:OBB = new OBB();
		Internal var m_vertices:Array = new Array(Settings._maxPolygonVertices);
		Internal var m_normals:Array = new Array(Settings._maxPolygonVertices);
		Internal var m_coreVertices:Array = new Array(Settings._maxPolygonVertices);
		Internal var m_vertexCount:int;

		static Internal function computeCentroid(vs:Array, count:int):Vec2 {
			//Settings.Assert(count >= 3);
		
			//Vec2 c; c = new Vec2(0.0f, 0.0f);
			var c:Vec2 = new Vec2();
			var area:Number = 0.0;
		
			// pRef is the reference point for forming triangles.
			// It's location doesn't change the result (except for rounding error).
			//Vec2 pRef(0.0f, 0.0f);
			var p1X:Number = 0.0;
			var p1Y:Number = 0.0;
			/*#if 0
			// This code would put the reference point inside the polygon.
			for (int32 i = 0; i < count; ++i)
			{
			pRef += vs[i];
			}
			pRef *= 1.0f / count;
			#endif*/
			var inv3:Number = 1.0 / 3.0;
		
			for (var i:int = 0;i < count; ++i) {
				// Triangle vertices.
				//Vec2 p1 = pRef;
				// 0.0, 0.0
				//Vec2 p2 = vs[i];
				var p2:Vec2 = vs[i];
				//Vec2 p3 = i + 1 < count ? vs[i+1] : vs[0];
				var p3:Vec2 = i + 1 < count ? vs[int(i + 1)] : vs[0];
			
				//Vec2 e1 = p2 - p1;
				var e1X:Number = p2.x - p1X;
				var e1Y:Number = p2.y - p1Y;
				//Vec2 e2 = p3 - p1;
				var e2X:Number = p3.x - p1X;
				var e2Y:Number = p3.y - p1Y;
			
				//float32 D = Cross(e1, e2);
				var D:Number = (e1X * e2Y - e1Y * e2X);
			
				//float32 triangleArea = 0.5f * D;
				var triangleArea:Number = 0.5 * D;
				area += triangleArea;
			
				// Area weighted centroid
				//c += triangleArea * inv3 * (p1 + p2 + p3);
				c.x += triangleArea * inv3 * (p1X + p2.x + p3.x);
				c.y += triangleArea * inv3 * (p1Y + p2.y + p3.y);
			}
		
			// Centroid
			//beSettings.Assert(area > Number.MIN_VALUE);
			//c *= 1.0 / area;
			c.x *= 1.0 / area;
			c.y *= 1.0 / area;
			return c;
		}

		// http://www.geometrictools.com/Documentation/MinimumAreaRectangle.pdf
		static Internal function computeOBB(obb:OBB, vs:Array, count:int):void {
			var i:int;
			//Settings.Assert(count <= Settings._maxPolygonVertices);
			var p:Array = new Array(Settings._maxPolygonVertices + 1);
			for (i = 0;i < count; ++i) {
				p[i] = vs[i];
			}
			p[count] = p[0];
		
			var minArea:Number = Number.MAX_VALUE;
		
			for (i = 1;i <= count; ++i) {
				var root:Vec2 = p[int(i - 1)];
				//Vec2 ux = p[i] - root;
				var uxX:Number = p[i].x - root.x;
				var uxY:Number = p[i].y - root.y;
				//var length:Number = ux.Normalize();
				var length:Number = Math.sqrt(uxX * uxX + uxY * uxY);
				uxX /= length;
				uxY /= length;
				//Settings.Assert(length > Number.MIN_VALUE);
				//Vec2 uy(-ux.y, ux.x);
				var uyX:Number = -uxY;
				var uyY:Number = uxX;
				//Vec2 lower(FLT_MAX, FLT_MAX);
				var lowerX:Number = Number.MAX_VALUE;
				var lowerY:Number = Number.MAX_VALUE;
				//Vec2 upper(-FLT_MAX, -FLT_MAX);
				var upperX:Number = -Number.MAX_VALUE;
				var upperY:Number = -Number.MAX_VALUE;
			
				for (var j:int = 0;j < count; ++j) {
					//Vec2 d = p[j] - root;
					var dX:Number = p[j].x - root.x;
					var dY:Number = p[j].y - root.y;
					//Vec2 r;
					//var rX:Number = Dot(ux, d);
					var rX:Number = (uxX * dX + uxY * dY);
					//var rY:Number = Dot(uy, d);
					var rY:Number = (uyX * dX + uyY * dY);
					//lower = Min(lower, r);
					if (rX < lowerX) lowerX = rX;
					if (rY < lowerY) lowerY = rY;
					//upper = Max(upper, r);
					if (rX > upperX) upperX = rX;
					if (rY > upperY) upperY = rY;
				}
			
				var area:Number = (upperX - lowerX) * (upperY - lowerY);
				if (area < 0.95 * minArea) {
					minArea = area;
					//obb->R.col1 = ux;
					obb.R.col1.x = uxX;
					obb.R.col1.y = uxY;
					//obb->R.col2 = uy;
					obb.R.col2.x = uyX;
					obb.R.col2.y = uyY;
					//Vec2 center = 0.5f * (lower + upper);
					var centerX:Number = 0.5 * (lowerX + upperX);
					var centerY:Number = 0.5 * (lowerY + upperY);
					//obb->center = root + Mul(obb->R, center);
					var tMat:Mat22 = obb.R;
					obb.center.x = root.x + (tMat.col1.x * centerX + tMat.col2.x * centerY);
					obb.center.y = root.y + (tMat.col1.y * centerX + tMat.col2.y * centerY);
					//obb->extents = 0.5f * (upper - lower);
					obb.extents.x = 0.5 * (upperX - lowerX);
					obb.extents.y = 0.5 * (upperY - lowerY);
				}
			}
		
		//Settings.Assert(minArea < Number.MAX_VALUE);
		}
	}
}
